{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#coding:utf-8\n",
    "import torch\n",
    "import pdb\n",
    "\n",
    "# 样本的特征，每个样本包含七个特征\n",
    "feature_space=[[1., 3., 2., 2., 3., 0.,3.], \n",
    "[2., 0., 2., 5., 1., 2.,3.], \n",
    "[3., 2., 3., 3., 2., 3.,2.], \n",
    "[4., 0., 3., 3., 2., 0.,1.], \n",
    "[3., 1., 2., 2., 5., 1.,3.], \n",
    "[1., 4., 3., 3., 1., 5.,2.], \n",
    "[3., 3., 3., 3., 1., 0.,1.], \n",
    "[5., 1., 1., 4., 2., 2.,2.], \n",
    "[6., 2., 3., 3., 2., 3.,0.], \n",
    "[2., 2., 2., 2., 5., 1.,4.]]\n",
    "\n",
    "\n",
    "def get_label(idx):\n",
    "    label= idx\n",
    "    return label\n",
    "\n",
    "#  计算以某个特征某个阈值进行分裂时的信息熵，即条件熵\n",
    "def cut_by_node(d,value,feature_space,list_need_cut):\n",
    "    # 分别存放以某个特征某个阈值分裂后的左右侧样本点\n",
    "    right_list=[]\n",
    "    left_list=[]\n",
    "    for i in list_need_cut:\n",
    "\n",
    "        if feature_space[i][d]<=value:\n",
    "             right_list.append(i)\n",
    "        else:\n",
    "             left_list.append(i)\n",
    "\n",
    "    left_list_t = list2label(left_list,[0,0,0,0,0,0,0,0,0,0])\n",
    "    right_list_t = list2label(right_list,[0,0,0,0,0,0,0,0,0,0])\n",
    "\n",
    "    e1=get_emtropy(left_list_t) \n",
    "    e2=get_emtropy(right_list_t) \n",
    "    n1 = float(len(left_list))\n",
    "    n2 = float(len(right_list))\n",
    "    e = e1*n1/(n2+n1) + e2*n2/(n1+n2)\n",
    "\n",
    "    return e,right_list,left_list\n",
    "\n",
    "# 将分到样本点转为one-hot各式，方便计算信息熵\n",
    "def list2label(list_need_label,list_label):\n",
    "     for i in list_need_label:\n",
    "         label=get_label(i)\n",
    "         list_label[label]+=1\n",
    "     return list_label\n",
    "\n",
    "def get_emtropy(class_list):\n",
    "   E = 0\n",
    "   sumv = float(sum(class_list))\n",
    "   if sumv == 0:\n",
    "       sumv =0.000000000001\n",
    "   for cl in class_list:\n",
    "       if cl==0:\n",
    "           cl=0.00000000001\n",
    "       p = torch.tensor(float(cl/sumv))\n",
    "       # log以2为底\n",
    "       E += -1.0 * p*torch.log(p)/torch.log(torch.tensor(2.))\n",
    "   return E.item()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_node(complate,d,list_need_cut):\n",
    "    # 初始时的信息熵，设为最大(根节点计算之前的信息熵)\n",
    "    e = 10000000\n",
    "    # node 代表以那个维度的那个特征值进行分裂\n",
    "    node=[]\n",
    "    # list_select:树分裂好的一个个结点序列，不包含已经分类好可以识别的结点\n",
    "    list_select=[]\n",
    "    # 存放可以识别的结点\n",
    "    complate_select=[]\n",
    "    # 0~8就是选择的阈值\n",
    "    for value in range(0,8):\n",
    "        complate_tmp=[]\n",
    "        etmp=0\n",
    "        list_select_tmp=[]\n",
    "        # 子序列总的长度\n",
    "        sumv=0.000000001\n",
    "        # 要进行分裂的所有结点序列\n",
    "        for lnc in list_need_cut:\n",
    "\n",
    "            # 计算条件熵，返回熵、左侧结点的样本点，右侧结点的样本点\n",
    "            etmptmp,r_list,l_list=cut_by_node(d,value,feature_space,lnc)\n",
    "            # 这行代码和etmp/sumv 就是求分裂后的总熵，就是那个pl*H1+pr*H2的公式\n",
    "            etmp+=etmptmp*len(lnc)\n",
    "            sumv+=float(len(lnc))\n",
    "            # 存放可以识别的结点\n",
    "            if len(r_list)>1:\n",
    "                list_select_tmp.append(r_list)\n",
    "            if len(l_list)>1:\n",
    "                list_select_tmp.append(l_list)\n",
    "            if len(r_list)==1:\n",
    "                complate_tmp.append(r_list)\n",
    "            if len(l_list)==1:\n",
    "                complate_tmp.append(l_list)\n",
    "            # print('子序列child:以每个样本的第{}个特征，特征值大小为{}划分{}子序列，得到的熵为{}'.format(d,value,lnc,etmptmp))    \n",
    "            \n",
    "        etmp = etmp/sumv\n",
    "        sumv=0\n",
    "        \n",
    "        # print('总序列All：以每个样本的第{}个特征，特征值大小为{}划分{}序列，得到的总熵为{}'.format(d,value,list_need_cut,etmp))    \n",
    "        \n",
    "        # 得到第n个特征以某一阈值分裂后的最小信息熵，及此时分裂后序列\n",
    "        if etmp<e:\n",
    "            e=etmp\n",
    "            node=[d,value]\n",
    "            list_select=list_select_tmp\n",
    "            complate_select=complate_tmp\n",
    "    for ll in complate_select:\n",
    "         complate.append(ll)\n",
    "    return node,list_select,complate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "node=[3, 2],complate=[],all_list=[[0, 4, 9], [1, 2, 3, 5, 6, 7, 8]]\n",
      "node=[4, 1],complate=[],all_list=[[0, 4, 9], [1, 5, 6], [2, 3, 7, 8]]\n",
      "node=[2, 2],complate=[[1], [7]],all_list=[[0, 4, 9], [5, 6], [2, 3, 8]]\n",
      "node=[5, 0],complate=[[1], [7], [0], [6], [5], [3]],all_list=[[4, 9], [2, 8]]\n",
      "node=[0, 2],complate=[[1], [7], [0], [6], [5], [3], [9], [4]],all_list=[[2, 8]]\n",
      "node=[1, 0],complate=[[1], [7], [0], [6], [5], [3], [9], [4]],all_list=[[2, 8]]\n",
      "node=[6, 0],complate=[[1], [7], [0], [6], [5], [3], [9], [4], [8], [2]],all_list=[]\n"
     ]
    }
   ],
   "source": [
    "import pdb\n",
    "def get_tree():\n",
    "#     pdb.set_trace()\n",
    "    # 10个样本：0, 1, 2, 3, 4, 5, 6, 7, 8, 9，注意是这里是二维数组\n",
    "    ## 二维数组里刚开始只有一个序列，即初始时只有一个根节点\n",
    "    all_list=[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]] \n",
    "    # complate的含义是：比如树的某个结点只有一个样本，那么存放到complate中\n",
    "    ## 即complate存放的是已经分类好的可以识别的结点\n",
    "    complate=[]\n",
    "    # 遍历样本的7个特征，这个序列就是遍历的先后顺序\n",
    "    ## d 首先遍历每个样本的第3个特征，把分类的结果返回\n",
    "    for d in [3,4,2,5,0,1,6]:\n",
    "        # node 代表以那个维度的那个特征值进行分裂\n",
    "        # all_list:树分裂好的一个个结点序列，不包含已经分类好可以识别的结点\n",
    "        node,all_list,complate=get_node(complate,d,all_list)\n",
    "        print(\"node=%s,complate=%s,all_list=%s\"%(node,complate,all_list))\n",
    "\n",
    "if __name__==\"__main__\":\n",
    "    get_tree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
